package com.algorithm.heap;/*
 *@Author:DOWN
 *@Date:2022/2/21 16:34
 *@Comment:堆排序
 */

public class HeapSort {
    /**
     * 私有方class
     */
    private HeapSort() {
    }

    /**
     * 传入泛型数组排序
     *
     * @param data 泛型数组
     * @param <E>  泛型
     */
    public static <E extends Comparable<E>> void sort(E[] data) {
        MaxHeap<E> maxHeap = new MaxHeap<>();
        for (E item : data) {
            maxHeap.add(item);
        }
        for (int i = data.length - 1; i >= 0; i--) {
            data[i] = maxHeap.extractMax();
        }
    }

    /**
     * 传入泛型数组排序-原地
     *
     * @param data 泛型数组
     * @param <E>  泛型
     */
    public static <E extends Comparable<E>> void sortCircleAround(E[] data) {
        //只有一个元素->退出
        if (data.length <= 1) {
            return;
        }
        //原地交换->从最后元素的父亲节点开始->下沉->生成最大堆
        for (int i = (data.length - 2) / 2; i >= 0; i--) {
            siftDown(data, i, data.length);
        }
        //最大值交换至尾节点->缩小交换范围->重新下沉->由最大堆生成排序。
        for (int i = data.length - 1; i >= 0; i--) {
            //交换
            E ret = data[i];
            data[i] = data[0];
            data[0] = ret;
            //下沉
            siftDown(data, 0, i);
        }
    }

    /**
     * 下沉元素
     *
     * @param data   泛型元素组
     * @param index  开始索引
     * @param length 调整范围
     * @param <E>    泛型
     */
    private static <E extends Comparable<E>> void siftDown(E[] data, int index, int length) {
        //index * 2 + 1:左节点索引
        while (index * 2 + 1 < length) {
            int j = index * 2 + 1;
            //比较左右节点大小
            if (j + 1 < length && data[j + 1].compareTo(data[j]) > 0) {
                j++;
            }
            //比较 index 与 子节点 的 大小
            if (data[index].compareTo(data[j]) >= 0) {
                break;
            }
            //交换位置
            E ret = data[index];
            data[index] = data[j];
            data[j] = ret;
            index = j;
        }
    }
}
